package algorithms.tree;

import java.util.List;

import algorithms.sort.ISort;

/**
 * 利用二叉搜索树的特征进行排序，时间复杂度能达到归并和快排的O(nlgn)的性能
 * 
 * 二叉搜索树本身就支持二分查找，需要O(lgn)的比较次数，<br>
 * 插入节点时，一旦找到插入位置，插入只需要常数级的O(1)的时间复杂度
 * 
 * @author shaoyuxia
 *
 * @param <T>
 */
public class BinarySearchTreeSort<T extends Comparable<T>> implements ISort<T> {

	@Override
	public T[] sort(T[] a) {
		BinarySearchTree<T> tree = new BinarySearchTree<>(a[0]);
		for (int i = 1; i < a.length;) {
			BinaryNode<T> node = new BinaryNode<T>(a[i++]);
			tree.insertNode(node);
		}
		List<T> list = tree.getSortedKeyList();
		return list.toArray(a);
	}

}
